Definition (decision problem)

Consider the problem of finding a maximum sized independent set (set of vertices without any common edges) in a graph. The corresponding language is

𝙸𝙽𝙳𝚂𝙴𝚃={⟨G,k⟩:∃S⊆V(G) s.t. |S|≥k and ∀u,v∈S,uv∉E(G)}\mathtt{INDSET} = \{\langle G,k\rangle : \exists S \subseteq V(G) \text{ s.t. } \lvert S \rvert \geq k \text{ and } \forall u, v \in S, \overline{uv} \notin E(G)\}

Algorithm to solve this language will tell, on inputting graph GG and number kk, where there exists an independent set of size at least kk.

Notes

References

  1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, pp. 3, 39.
  2. https://web.stanford.edu/class/archive/cs/cs103/cs103.1142/lectures/28/Small28.pdf
  3. https://people.engr.tamu.edu/andreas-klappenecker/csce658-s18/complexity.pdf